/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年04月14日
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
================================================================*/


#include <iostream>

using namespace std;

class Solution {
public:
    int longestSubstring(string s, int k) {
        int size = s.size();
        return findSubstring(0, size - 1, k, s);
    }
private:
    int findSubstring(int left, int right, int k, string &s){
        if(right < left)
            return 0;

        int count[26] = {0};
        int maxRes = INT_MIN;

        for(int i = left; i <= right; i++){
            count[s[i] - 'a'] += 1;
        }

        for(left; left <= right && count[s[left] - 'a'] < k; left++){
            count[s[left] - 'a'] -= 1;
        }

        for(right; left <= right && count[s[right] - 'a'] < k; right--){
            count[s[right] - 'a'] -= 1;
        }

        for(int index = left + 1; index < right; index++){
            if(count[s[index] - 'a'] < k){
                maxRes = max(findSubstring(left, index - 1, k, s), findSubstring(index + 1, right, k, s));
            }
        }

        if(maxRes == INT_MIN){
            maxRes = right - left + 1;
        }

        return maxRes;
    }
};

